The present invention relates to the rendering of object graphic elements into raster pixel images and, in particular, to efficient rendering of such elements to pixel image data without the use of frame or line storage of the pixel data as part of the rendering process.
Most object based graphics systems utilise a frame store or page buffer to hold a pixel-based image of the page or screen. Typically, the outlines of the graphic objects are calculated, filled and written into the frame store. For two-dimensional graphics, objects which appear in front of other objects are simply written into the frame store after the background objects, thereby replacing the background on a pixel-by-pixel basis. This is commonly known in the art as the xe2x80x9cPainter""s algorithmxe2x80x9d. Objects are considered in priority order, from the rearmost object to the foremost object, and, typically, each object is rasterised in scan line order and pixels are written to the frame store in sequential runs along each scan line.
There are essentially two problems with this technique. The first is that it requires fast random access to all the pixels in the frame store. This is because each new object considered could affect any pixel in the frame-store. For this reason, the frame store is normally kept in semiconductor random access memory (RAM). For high resolution colour printers the amount of RAM required is very large, typically in excess of 100 MBytes, which is costly and difficult to operate at high speed. The second problem is that many pixels which are painted (rendered), are over-painted (re-rendered) by later objects. Painting the pixels with the earlier objects was a waste of time.
One method for overcoming the large frame-store problem is the use of xe2x80x9cbandingxe2x80x9d. When banding is used, only part of the frame-store exists in memory at any one time. All of the objects to be drawn are retained in a xe2x80x9cdisplay listxe2x80x9d. The whole image is rendered as above, but pixel painting (rendering) operations that try to paint (render) outside the fraction of the frame-store which exists are xe2x80x9cclippedxe2x80x9d out. After all the objects have been drawn, the fractional part of the frame-store is sent to the printer (or some other location) and another fraction of the frame-store is selected and the process repeated. There are penalties with this technique. For example, the objects being drawn must be considered and re-considered many timesxe2x80x94once for each band. As the number of bands increases, so too does the repetitious examination of objects requiring rendering. The technique of banding does not solve the problem of the cost of over-painting.
Some other graphic systems consider the image in scan line order. Again, all the objects to be drawn are retained in a display list. On each scan line the objects which intersect that scan line are then considered in priority order and for each object, spans of pixels between object edge intersection points are set in a line store. This technique also overcomes the large frame store problem, but still suffers from the over-paint problem.
There are other techniques which overcome both the large frame-store problem and the over-painting problem. In one such technique, each scan line is produced in turn Again, all the objects to be drawn are retained in a display list. On each scan line, the edges of objects which intersect that scan line are held in order of increasing coordinate of intersection with the scan line. These points of intersection, or edge crossings, are considered in turn and used to toggle an array of active flags. There is one active flag for each object priority which is of interest on the scan line. Between each pair of edges considered, the colour data for each pixel which lies between the first edge and the next edge is generated by using a priority encoder on the active flags to determine which priority is topmost, and using the colour associated with that priority for the pixels of the span between the two edges. In preparation for the next scan line, the coordinate of intersection of each edge is updated in accordance with the nature of each edge. Adjacent edges which become mis-sorted as a result of this update are swapped. New edges are also merged into the list of edges.
This technique has the significant advantages that there is no frame store or line store, there is no over painting, and the object priorities are dealt with in constant order time, rather than order N time (where N is the number of priorities).
However, there are several limitations to this technique:
(i) The technique only supports the xe2x80x9codd-evenxe2x80x9d fill rule, known in the art for determining the inside versus outside state of an object from its edges. The xe2x80x9cnon-zero windingxe2x80x9d fill rule, which is a required feature of many graphic description languages, is not supported by that technique.
(ii) Large mis-sorting can occur for which a simple swapping technique is inadequate to repair. While a brute-force sort of the whole of the edge list on each scan line can be performed, this is very slow.
(iii) The technique does not support raster (pixel-based) images as an object type. Such images are a required feature of most graphic description languages.
(iv) The technique only supports objects which are opaque, where each painted pixel strictly obscures the pixels of objects with lesser priority. The technique does not support raster operations in which the colour of two or more graphic objects interact. Such operations include drawing in XOR mode, or the compositing of partially transparent objects. These modification operations are a required feature of most graphic description languages.
(v) The technique does not support clipping, where one or more clip shapes suppress some number of other graphics objects inside (or outside) the bounds of the clip shapes. Clipping is a required feature of most graphic description languages.
(vi) The technique uses voluminous and inefficient encoding of object edges, particularly for text. It is desirable for such an extremely common element of graphic descriptions to be represented in a simpler fashion.
(vii) The technique in some instances does not provide for accurate evaluation of complicated compositing expressions where the activity of one or more objections is variable.
The inability of the technique to implement many features required by existing graphic description languages severely limits its use.
Further, some existing rendering interfaces require implementation of the bit-wise logical combination of the colour of two or more graphic objects. Other existing rendering interfaces require implementation of an alpha channel (also referred to as transparency, opacity, or matte) based combination of the colour of two or more graphic objects. Current techniques do not allow these two features to be implemented in a unified fashion.
It is an object of the present invention to substantially overcome, or at least ameliorate, one or more deficiencies with prior art systems.
In accordance with one aspect of the present invention there is disclosed a method of rendering at least one graphic object described by at least one edge into a raster pixel image having a plurality of scan lines and a plurality of pixel locations on each said scan line, said method comprising, for each said scan line, the steps of:
determining in a predetermined order coordinates of intersection of those edges of said objects that intersect said scan line;
for each adjacent pair of edge intersections, examining information associated with the corresponding said object to determining a set of active objects for a span of pixel locations between the corresponding pair of edge intersections; and
for each said span of pixel locations, using the corresponding set of active objects to determine a value for each of said locations within said span.
In accordance with another aspect of the present invention there is disclosed a method of rendering a plurality of graphic objects described by at least one edge to form a raster pixel image having a plurality of scan lines and a plurality of pixel locations on each said scan line, said method comprising, for each said scan line, the steps of:
(a) determining in a predetermined order coordinates of intersection of those edges of said objects that intersect said scan line;
(b) for each edge intersection so determined, modifying an integral fill count associated with the corresponding said object;
(c) for each adjacent pair of edge intersections, examining the corresponding fill counts to determine a set of said objects active for a span of pixel locations between the corresponding pair of edge intersections; and
(d) for each said span of pixel locations, using the corresponding set of active objects to determine a value for each of said pixel locations within said span.
In accordance with another aspect of the present invention there is disclosed a method of rendering a plurality of graphic objects, each having an associated rendering level, to form a raster pixel image having a plurality of scan lines and a plurality of pixel locations on each said scan line, each said object having at least one corresponding filled region defined by intersections of said scan lines by edge of said object, said intersections defining for each said scan line a corresponding fill count through application of the non-zero winding fill rule, said method being characterised by the simultaneous storage of a plurality of said fill counts, and using said stored fill counts to determine those said rendering levels that contribute to said image.
In accordance with another aspect of the present invention there is disclosed a method of rendering a plurality of graphic objects to form a raster pixel image having a plurality of scan lines and a plurality of pixel locations on each said scan line, each said object being described by components including at least one edge, a viewing priority and fill data, said method comprising the steps of:
(a) establishing records corresponding to each said component and associating said component records each with a corresponding component process;
(b) rendering said graphic objects in a rasterised fashion by activating said component processes, CHARACTERISED BY, for each said scan line, the steps of
(c) determining in a predetermined order coordinates of intersection of those edges of said objects that intersect said scan line;
(d) for each edge intersection so determined, updating a level activation table forming at least part of said viewing priority records, said level activation table being arranged according to object viewing priority and including plural entries corresponding to at least an integral fill count associated with the corresponding said object;
(e) for each adjacent pair of edge intersections, examining at least plural ones of said entries of said level activation table to determine a set of said objects active for a span of pixel locations between the corresponding pair of edge intersections; and
(f) for each said span of pixel locations, using the corresponding set of active objects to determine a rendered value for each of said pixel locations within said span.
In accordance with another aspect of the present invention there is disclosed a method of rendering a plurality of overlapping graphic objects having variable opacity and described by at least one edge to form a raster pixel image having a plurality of scan lines and a plurality of pixel locations on each said scan line, said method comprising, for each said scan line, the steps of:
(a) determining in a predetermined order coordinates of intersection of those edges of said objects that intersect said scan line;
(b) for each edge intersection so determined, updating a record of contribution indicators associated with the corresponding said objects;
(c) for each adjacent pair of edge intersections, examining the corresponding contribution indicators to determine a (first) set of said objects that contribute to pixel values in a span of pixel locations between the corresponding edge intersections; and
(d) for each said span of pixel locations, using the corresponding (first) set of said objects to determine a value for each of said pixel locations within said stack.
In accordance with another aspect of the present invention there is disclosed a method of rendering a plurality of overlapping graphic objects having variable opacity and described by at least one edge into a raster pixel image having a plurality of scan line and a plurality of pixel locations on each said scan line, said method comprising the steps of:
forming a plurality of stack records of colour and opacity values for a plurality of active objects to be rendered in a current scan line of said image;
identifying those ones of said objects that contribute to pixel values within a span of pixel locations between adjacent edge intersections of said objects;
for those identified objects within each said span, receiving a compositing message and determining therefrom at least one compositing operation for each said record in said stack;
using said at least one compositing operation and corresponding said colour and opacity values, to determine an output pixel value for each pixel location within said span by compositing the stack records.
In accordance with another aspect of the present invention there is disclosed a method of rendering a plurality of overlapping graphic objects having variable opacity and described by at least one edge into a raster pixel image having a plurality of scan lines and a plurality of pixel locations on each said scan line, said method comprising, for each said scan line, the steps of:
(a) determining in a predetermined order coordinates of intersection of those edges of said objects that intersect said scan line;
(b) for each edge intersection so determined, forming a plurality of stack records of colour and opacity values for a plurality of active objects to be rendered in a current scan line of said image and updating a record of contribution indicators associated with the corresponding said objects;
(c) for each adjacent pair of edge intersections, examining at least the corresponding contribution indicators to determine a (first) set of said objects that contribute to pixel values in a span of pixel locations between the corresponding edge intersections; and
(d) for those identified objects within said first set of each said span, receiving a compositing message and determining therefrom at least a compositing operation for each said record in said stack;
(e) for each said span of pixel locations, using the corresponding (first) set, said compositing operations and the corresponding said colour and opacity values, to determine an output pixel value for each pixel location within said span by compositing the stack records.
In accordance with another aspect of the present invention there is disclosed a method of rendering a plurality of graphic objects each having at least one edge to form a raster pixel image including a plurality of scan lines and a plural of pixel locations within each said scan line, said computer program product being configured to implement, for each said scan line, the steps of:
(a) determining in a predetermined order coordinates of intersection of those of said objects that intersect said scan line;
(b) for each edge intersection so determined, modifying an integral clip count associated with the corresponding said object;
(c) for each adjacent pair of edge intersections, examining the corresponding clip counts to determine a set of said objects that contribute to said raster pixel image for a span of pixel locations between the corresponding pair of edge intersections; and
(d) for each said span of pixel locations, using the corresponding set of contributing objects to determine a value for each said pixel location within said span.
In accordance with another aspect of the present invention there is disclosed a method of rendering a plurality of graphic objects each having at least one edge to form a raster pixel image including a plurality of scan lines and a plural of pixel locations within each said scan line, said method comprising, for each said scan line, the steps of:
(a) determining in a predetermined order coordinates of intersection of those of said objects that intersect said scan line;
(b) for each edge intersection so determined, modifying each of an integral fill count and an integral clip count associated with the corresponding said object;
(c) for each adjacent pair of edge intersections, examining the corresponding fill counts and clip counts to determine a set of said objects that contribute to said raster pixel image for a span of pixel locations between the corresponding pair of edge intersections; and
(d) for each said span of pixel locations, using the corresponding set of contributing objects to determine a value for each said pixel location within said span.
In accordance with another aspect of the present invention there is disclosed a method of rendering at least one graphic object described by at least one edge to form a raster pixel image having a plurality of scan lines and a plurality of pixel locations on each said scan line, said method comprising, for each said scan line, the steps of:
(a) determining in a predetermined order coordinates of intersection of those edges of said objects that intersect said scan line;
(b) for each edge intersection so determined, updating a table of those said objects current on said scan line, said table including an independence entry for each said object indicating that a colour reproduced by said object is independent of a position within said object;
(c) for each adjacent pair of edge intersections, examining said table to determine a set of said objects active for a span of pixel locations between the corresponding pair of edge intersections and forming a rendering instruction based upon said set of objects, said rendering instruction including an indicator that is valid when each of the objects of said set has a corresponding valid independence entry; and
(d) determining rendered pixel values using said rendering instruction and said indicator.
In accordance with another aspect of the present invention there is disclosed a method of rendering at least one graphic object described by at least one edge into a raster pixel image having a plurality of scan lines and a plurality of pixel locations on each said scan line, each said graphic object including an independence entry indicating that a colour reproduced by said object is independent of a position within said object, said method comprising, for each said scan line, the steps of:
(a) determining in a predetermined order coordinates of intersection of those edges of said objects that intersect said scan line;
(b) for each adjacent pair of edge intersections, determining a set of said objects active for a span of pixel locations between the corresponding pair of edge intersections and forming a rendering instruction based upon said set of objects, said rendering instruction including an indicator that is valid when each of the objects of said set has a corresponding valid independence entry; and
(c) determining rendered pixel values using said rendering instruction and said indicator.
In accordance with another aspect of the present invention there is disclosed a method of generating a repeat rendering message in graphic object rendering, said method being characterised by providing each said graphic object with a flag indicative of an independence of said object to a change in pixel colour whereby when a set of said objects are to be rendered simultaneously for a span of pixel locations, an indicator for said set is made valid if each of the objects in the set has a valid independence flag so that only a first pixel of said span need be rendered and thereafter that pixel is repeatedly output until the end of the span.
Other aspects of the present invention including corresponding apparatus and computer readable media will be apparent from the following description.